It is well known in the art that wireless transmitters and receivers called Access Points (“APs”) may be physically attached to Local Area Networks (“LANs”) such as Ethernet networks conforming to IEEE standard 802.3. Following the IEEE 802.11b standard, Mobile Stations may be connected to the APs through the transmission and reception of radio signals.
As Mobile Stations transmit information to an AP, the AP may either broadcast the information to other wirelessly connected Mobile Stations or may pass the information to the attached Ethernet. Signals originating from the wired LAN can be transmitted to Mobile Station by way of the AP. In this manner, a computer, personal digital assistant (“PDA”), or other digital device physically connected to an Ethernet LAN can communicate with Mobile Stations which are wirelessly connected to APs and vice versa. Additionally, Mobile Stations may communicate with other Mobile Stations which are wirelessly connected to the same AP or are connected through the wired LAN to another AP.
The IEEE 802.11b specification allows for the wireless transmission of approximately 11 million bits per second (“Mbps”) of digital data at indoor distances up to a few hundred feet and outdoor distances up to tens of miles on a 2.4 gigahertz (“GHz”) radio broadcast band. 802.11b is an extension of wired Ethernet, the backbone of most LANs, which is specified by the IEEE 802.3 standard. The wireless broadcast band is primarily used for Internet protocol based communication, but can be used for just about any type of digital communication. The area of effective transmission and reception depends on transmission strength, reception antennae, and line-of-sight obstructions. Other competing technologies making use of the 2.4 GHz broadcast band are BlueTooth and HomeRF.
A standard procedure for regulating data transmission between computing devices is called a communications protocol. While numerous protocols are available for data transmission, all communications protocols must provide for certain core functions. These functions may be implemented differently by different product vendors. An Open Systems Interconnection (“OSI”) reference model, created by the International Organization for Standardization (“ISO”), provides the basic model for digital data communications protocols.
The OSI reference model has seven layers, each layer being responsible for different communications functionality. Layer 1 is the Physical layer, defining the hardware, connectors, cables, and signaling specifications. Layer 2 is the Data Link layer, responsible for moving packets of data. The Data Link layer is comprised of two sub-layers: (1) the Media Access Control (“MAC”) layer, which assembles bytes of data arriving from the Physical layer into data frames (or, vice versa), and (2) the Logical Link Layer (“LLC”), which arranges data frames into data packets.
Layer 3 is the Network or Internet layer. The Network layer is responsible for routing data packets through communications networks. Routers, operating at this level, can be used to connect communications devices that use different Data Link and Physical layer technology, as the Network layer operates without regard to underlying protocol layers. Each router or other device connected to a digital data communications network, following the OSI model, has a Layer 3 address, called its Internet Protocol (“IP”) address.
Layer 4 is the Transport Layer, responsible for creating a virtual communications path between two devices for the transmission of messages. Layer 5 (Session Layer), Layer 6 (Presentation Layer), and Layer 7 (Application Layer), utilize the underlying layers to transmit and receive digital data.
A User Data Protocol (“UDP”) is a Transport layer protocol responsible for end-to-end transmission of data on a communications network. It is a best-effort attempt to send data and does not attempt to verify that the target has actually received the message.
Both the IEEE 802.3 wired network standard and the IEEE 802.11 wireless network standard utilize a 6-byte MAC layer hardware addressing scheme. Each device connected to these networks possesses a MAC address. These Layer 2 addresses are unique for each vendor and device and contain no Network layer (Layer 3) routing information. The first three bytes contain a vendor specific designation number and the final three bytes contain the unique device number. The MAC layer address is typically represented by six hexadecimal numbers separated by colons such as:                00:D0:DC:67:72:3FAlthough simple communications bridges between two devices may be made using Layer 2 protocols, such simple bridges are inefficient for complex routing involving multiple communications subnets or multiple transmission hops. Additionally, Layer 2 bridges cannot accommodate hardware devices or subnets utilizing different Layer 2 protocols. For efficient Network layer communication, routers generally utilize a Layer 3 protocol such as the Internet Version 4 (“IPV4”).        
All IPV4 protocol addresses are four bytes long and contain a network address and host identification number:                172.16.0.10Ultimately, however, a communications network must translate these IPV4 (IP) addresses to MAC (hardware) addresses for data to reach the desired hardware device.        
Address Resolution Protocol (“ARP”) is the Internet layer protocol (operating at the OSI Network layer) responsible for determining the hardware address (Layer 2 MAC address) which corresponds to a particular IP address. Devices utilizing ARP possess a memory cache containing a translation table for mapping IP addresses into MAC addresses. Before a data packet can be sent to a specific hardware device, the MAC address of the receiving device must be known. Transmitting devices (such as routers) first check their ARP cache to determine whether the MAC address of the target is in its translation table. If the MAC address exists in the table, the message is sent directly to the receiving device.
If the destination's MAC address is not present, the transmitting device sends a Network layer Broadcast Request containing the target's IP (Layer 3) address to all devices attached to the communications network. The communication device which is associated with the IP address then transmits a response which includes its corresponding MAC address. This MAC address is then added to the requesting device's ARP cache table for future use.
ARP messages are either Requests for MAC addresses or Replies providing MAC addresses. Each ARP transmission contains the following fields:
FieldSize(bits)DescriptionHAS16Hardware Address SpacePAS16Protocol Address SpaceHAL8Hardware Address LengthPAL8Protocol Address LengthOP16Operation CodeSMAC48Source MAC AddressSIP32Source IP AddressDMAC48Destination MAC AddressDIP32Destination IP Address
The ARP cache maintains a translation table of MAC address and IP address pairs similar to the following:                00:D0:DC:67:72:3F 172.16.200.4        00:D0:DC:67:72:3F 172.17.0.4        00:D0:DC:68:99:73 172.17.0.10        00:D0:DC:27:35:32 172.17.0.11        00:D0:DC:43:89:64 172.17.0.12        00:D0:DC:5B:8F:35 172.17.0.100        
In typical bridged communications networks, ARP requests are Broadcast messages (messages transmitted from a single source to all connected communications devices), flooding the entire communications network in order to locate a single device's MAC address. One problem with 802.11 wireless networks is that they incur a high percentage of lost packets (packets which are transmitted by one device, but are not received by the target). For this reason, the 802.11 standard requires the re-transmission of Unicast messages (messages transmitted from a single source device to a single target device) until the target device acknowledges receipt. However, this re-transmission requirement does not apply to Broadcast messages.
802.11 wireless networks typically experience packet loss rates of 10-20%, making broadcast messaging extremely unreliable. The reliability of wireless networks decreases dramatically as messages are re-transmitted along the network, resulting in transmissions. For example, suppose that each wireless transmission experiences a packet loss rate of 20%. For Unicast messages, 1 in 5 packets must be re-transmitted for each transmission. For Broadcast messages, however, each successive transmission results in compounding of the amount of lost packets. After two hops, only 64% of transmissions would reach their target devices. After three hops, the success rate is just slightly greater than 50%. This compound deterioration of packet delivery makes the IEEE 802.11 wireless standard, in and of itself, almost unusable as a transmissions.
An additional problem of multi-hop wireless networks is that they are susceptible to hardware failure, interference, and changes in transmission quality due to atmospheric conditions. If a transmission from a LAN requires multiple retransmissions by APs to reach a Mobile Station, a failure of a single AP will prevent the message from reaching its target. Additionally, if an AP is taken off-line for maintenance, the same result occurs. In a dynamically changing environment, such as a strip-mine site, Mobile Stations sometimes change location so that their transmission path to their associated APs are blocked by terrain, buildings, or vehicles.
For these reasons, it is desirable to have a wireless network system which can dynamically configure itself to adapt to changes in the AP network. It is also desirable to have a wireless network system which is resilient to hardware failures, changes in atmospheric conditions, and interference of transmission paths. It is further desirable to have a wireless network which efficiently transmits messages between Mobile Stations, without flooding the communications network.